package com.liying;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.json.JSONArray;
import org.json.JSONObject;

/**
 * �ڽӱ�����ͼ
 * 
 * @author ly
 * 
 */
public class Graph {

	private int vectorNum;
	private int edgeNum;
	private ArrayList<Node> nodes;
	private HashMap<String, ArrayList<Edge>> adjaxTable;

	public Graph(int vectorNum, int edgeNum, ArrayList<Node> nodes) {
		this.vectorNum = vectorNum;
		this.edgeNum = edgeNum;
		adjaxTable = new HashMap<String, ArrayList<Edge>>();
		this.nodes = nodes;
	}

	public Graph(int vectorNum, int edgeNum) {
		this(vectorNum, edgeNum, new ArrayList<Node>());
	}

	public int getVectorNum() {
		return vectorNum;
	}

	public void setVectorNum(int vectorNum) {
		this.vectorNum = vectorNum;
	}

	public void setEdgeNum(int edgeNum) {
		this.edgeNum = edgeNum;
	}

	public int getEdgeNum() {
		return edgeNum;
	}

	public HashMap<String, ArrayList<Edge>> getAdjaxTable() {
		return adjaxTable;
	}

	public ArrayList<Node> getNodes() {
		return nodes;
	}

	public Node findNode(String id) {
		if (nodes != null) {
			for (Node node : nodes) {
				if (node.getId().equals(id)) {
					return node;
				}
			}
		}

		return null;
	}

	public void addEdge(String id, String source, int state, String target,
			float value) {

		if (adjaxTable.containsKey(source)) {
			adjaxTable.get(source).add(
					new Edge(id, source, state, target, value));
		} else {
			ArrayList<Edge> al = new ArrayList<Edge>();
			al.add(new Edge(id, source, state, target, value));
			adjaxTable.put(source, al);
		}
	}

	/**
	 * ���һ���ڵ�����б�
	 * 
	 * @param fromNode
	 * @param neighbors
	 */
	public void addEdges(String source, Set<String> neighbors) {
		ArrayList<Edge> al = new ArrayList<Edge>();
		int edgeId = 0;
		for (String neighbor : neighbors) {
			al.add(new Edge((edgeId + 1) + "", source, 0, neighbor, 1));
		}

		if (adjaxTable.containsKey(source)) {
			adjaxTable.get(source).addAll(al);
		} else {
			adjaxTable.put(source, al);
		}
	}

	/**
	 * ���ȫ����
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public ArrayList<Edge> getAllEdges() {
		ArrayList<Edge> list = new ArrayList<Edge>();

		Iterator iter = getAdjaxTable().entrySet().iterator();
		while (iter.hasNext()) {
			Map.Entry entry = (Map.Entry) iter.next();
			ArrayList<Edge> edges = (ArrayList<Edge>) entry.getValue();
			list.addAll(edges);
		}

		return list;
	}

	/**
	 * ��ӽڵ����
	 * 
	 * @param din
	 * @param dout
	 * @param dtotal
	 * @param name
	 * @param state
	 */
	public void addNode(int din, int dout, int dtotal, String id, String label,
			double size, int state, double x, double y) {
		if (nodes == null) {
			nodes = new ArrayList<Node>();
		}

		nodes.add(new Node(din, dout, dtotal, id, label, size, state, x, y));
	}

	/**
	 * ��ýڵ�fromNode���ھӼ���
	 * 
	 * @param fromNode
	 */
	public HashSet<String> getNeighbors(String source) {
		HashSet<String> neighbors = new HashSet<String>();
		for (Edge edge : getAdjaxTable().get(source)) {
			neighbors.add(edge.getTarget());
		}

		return neighbors;
	}

	/**
	 * ��ӡͼ��Ϣ
	 * 
	 * @param printScore
	 *            �Ƿ��ӡ�÷�
	 */
	@SuppressWarnings({ "unchecked", "rawtypes" })
	public void print(boolean printScore) {
		Iterator iter = getAdjaxTable().entrySet().iterator();
		while (iter.hasNext()) {
			Map.Entry entry = (Map.Entry) iter.next();
			String node = (String) entry.getKey();
			ArrayList<Edge> edges = (ArrayList<Edge>) entry.getValue();

			System.out.println(node + " ========");
			for (Edge edge : edges) {
				if (printScore)
					System.out.println(edge.getSource() + "=>"
							+ edge.getTarget() + ":  " + edge.getValue());
				else
					System.out.println(edge.getSource() + "=>"
							+ edge.getTarget());
			}

			System.out.println();
		}

	}

	/**
	 * �ҳ�10���÷���ߵı�
	 */
	@SuppressWarnings({ "unchecked", "rawtypes" })
	public List<Edge> findTops(int topNum) {
		ArrayList<Edge> allEdges = new ArrayList<Edge>();
		Iterator iter = adjaxTable.entrySet().iterator();
		while (iter.hasNext()) {
			Map.Entry entry = (Map.Entry) iter.next();
			ArrayList<Edge> edges = (ArrayList<Edge>) entry.getValue();
			allEdges.addAll(edges);
		}

		Collections.sort(allEdges, new Comparator<Edge>() {
			@Override
			public int compare(Edge arg0, Edge arg1) {
				return ((Float) arg1.getValue()).compareTo((Float) arg0
						.getValue());
			}
		});

		System.out.println("\nTop N ====================");
		for(int i=0; i<topNum; i++){
			Edge e = allEdges.get(i);
			System.out.println(e.getId() + ":" + e.getSource() + "=>" + e.getTarget() + ":" + e.getValue());
		}
		System.out.println("Top N ====================\n");
		
		return allEdges.subList(0, topNum);
	}
	
	
	/**
	 * 构建该图的补图
	 * 
	 * @return
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public Graph buildComplementGraph() {
		Graph complementGraph = null;
		complementGraph = new Graph(vectorNum, vectorNum * vectorNum - edgeNum,
				nodes);

		HashSet<String> allNodes = new HashSet<String>();
		for (int i = 0; i < vectorNum; i++) {
			allNodes.add(Integer.toString(i));
		}

		Iterator iter = adjaxTable.entrySet().iterator();
		while (iter.hasNext()) {
			Map.Entry entry = (Map.Entry) iter.next();
			String node = (String) entry.getKey();
			ArrayList<Edge> edges = (ArrayList<Edge>) entry.getValue();

			HashSet<String> toNodes = new HashSet<String>();
			for (Edge edge : edges) {
				toNodes.add(edge.getTarget());
			}

			complementGraph.addEdges(node,
					SetOperation.getSubtraction(allNodes, node, toNodes));
		}

		return complementGraph;
	}
}
